/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package fi.uba.algo3.tp3.utils.dijkstra;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 *
 * @author Ezequiel
 */
public class Dijkstra {

    /**
     *
     * @param source
     */
    public static void calcularCamintosDesde(Vertice source) {
        source.setDistanciaMinima(0.0);

        PriorityQueue<Vertice> vertexQueue = new PriorityQueue<Vertice>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertice u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Camino e : u.getCaminos()) {
                Vertice v = e.getTarget();
                double peso = e.getWeight();
                double distanceThroughU = u.getDistanciaMinima() + peso;
                if (distanceThroughU < v.getDistanciaMinima()) {
                    vertexQueue.remove(v);
                    v.setDistanciaMinima(distanceThroughU);
                    v.setPrevio(u);
                    vertexQueue.add(v);
                }
            }
        }
    }

    public static List<Vertice> menorCaminoHasta(Vertice target) {
        List<Vertice> path = new ArrayList<Vertice>();
        for (Vertice vertex = target; vertex != null; vertex = vertex.getPrevio()) {
            path.add(vertex);
        }

        Collections.reverse(path);
        return path;
    }
}
